/*
   @Copyright:LintCode
   @Author:   tjyemail
   @Problem:  http://www.lintcode.com/problem/longest-ab-substring
   @Language: C++
   @Datetime: 19-03-14 14:50
   */

class Solution {
public:
	/**
	 * @param S: a String consists of a and b
	 * @return: the longest of the longest string that meets the condition
	 */
	int getAns(string &S) {
		// Write your code here
		if (S.length()<2) return 0;
		unordered_map<int,int> sums;    // sum, indexs
		sums[0]=-1;
		int max=0;
		for(int i=0, sum=0; i<S.length(); ++i){
			sum += (S[i]=='A'?1:-1);
			unordered_map<int,int>::iterator it=sums.find(sum);
			if (it!=sums.end()){
				int m=i-(it->second);
				max=max<m ? m:max;
			}
			else sums[sum]=i;
		}
		return max;
	}
};
